//家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐
//行逐列 地整理每个格子。 
//
// 整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > 
//cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。 
//
// 请返回整理师 总共需要整理多少个格子。 
//
// 
//
// 示例 1： 
//
// 
//输入：m = 4, n = 7, cnt = 5
//输出：18
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n, m <= 100 
// 0 <= cnt <= 20 
// 
//
// 
//
// Related Topics 深度优先搜索 广度优先搜索 动态规划 👍 686 👎 0


package LeetCode.editor.cn;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2025-04-27 17:49:18
 * @description LCR 130.衣橱整理
 
 */
 
public class JiQiRenDeYunDongFanWeiLcof {
    public static void main(String[] args) {
    //测试代码
    JiQiRenDeYunDongFanWeiLcof fun = new JiQiRenDeYunDongFanWeiLcof();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //问题在于不能直接双重循环，因为有可能旁边的不能到，但是当前格子又合法
    //所以必须首先可达，然后再计数
        //bfs  不断加入每个右和下
    public int wardrobeFinishing1(int m, int n, int cnt) {
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            if (digitSum(i) + digitSum(j) <= cnt) {
                count++;
                // Move right
                if (j + 1 < n && !visited[i][j + 1]) {
                    visited[i][j + 1] = true;
                    queue.offer(new int[]{i, j + 1});
                }
                // Move down
                if (i + 1 < m && !visited[i + 1][j]) {
                    visited[i + 1][j] = true;
                    queue.offer(new int[]{i + 1, j});
                }
            }
        }
        return count;
    }
    private boolean[][] visited;
    private int count;
    private int m;
    private int n;
    private int cnt;
    //dfs
    public int wardrobeFinishing2(int m, int n, int cnt) {
        this.m = m;
        this.n = n;
        this.cnt = cnt;
        this.visited = new boolean[m][n];
        this.count = 0;
        dfs(0, 0);
        return count;
    }

    private void dfs(int i, int j) {
        if (i >= m || j >= n || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        if (digitSum(i) + digitSum(j) <= cnt) {
            count++;
            dfs(i + 1, j); // Move down
            dfs(i, j + 1); // Move right
        }
    }
    private int digitSum(int x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    //动态规划
    public int wardrobeFinishing(int m, int n, int cnt) {
        boolean[][] dp = new boolean[m][n];
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = digitSum(i) + digitSum(j) <= cnt;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && (digitSum(i) + digitSum(j) <= cnt);
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && (digitSum(i) + digitSum(j) <= cnt);
                } else {
                    dp[i][j] = (dp[i - 1][j] || dp[i][j - 1]) && (digitSum(i) + digitSum(j) <= cnt);
                }
                if (dp[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
